package com.study.algorithm.linkedList;

import java.util.ArrayList;
import java.util.List;

public class IsPalindrome {
    /**
     * 方法1：数组存储法
     * 时间复杂度：O(n) 空间复杂度：O(n)
     */
    public boolean isPalindrome1(ListNode head) {
        List<Integer> vals = new ArrayList<>();
        //将链表存入集合
        ListNode curr = head;
        while (curr != null) {
            vals.add(curr.val);
            curr = curr.next;
        }
        //双指针对比是否是回文
        int left = 0, right = vals.size() - 1;
        while (left < right) {
            if (!vals.get(left).equals(vals.get(right)))
                return false;
            left++;
            right--;
        }
        return true;
    }

    /**
     * 方法3：快慢指针+反转链表（最优解）
     * 时间复杂度：O(n) 空间复杂度：O(1)
     */
    public boolean isPalindrome(ListNode head) {
        // 边界处理
        if (head == null || head.next == null) return true;
        // 第一步：快慢指针找中点
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 处理奇数长度情况
        if (fast != null) slow = slow.next;   // 如果fast不为null，说明链表长度为奇数，跳过中点，让slow指向后半部分的起点
        // 第二步：反转后半部分链表
        ListNode reversed = reverseList(slow);
        // 第三步：比较前后两部分
        while (reversed != null) {
            if (head.val != reversed.val) return false;
            //指针后移
            head = head.next;
            reversed = reversed.next;
        }
        return true;
    }

    // 辅助方法：反转链表
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {

            ListNode next = head.next;  //  保存当前节点的下一个节点
            head.next = prev; //  反转指针方向
            prev = head; // 前驱节点后移：prev 指向当前节点（成为新的反转部分头节点）
            head = next;   // 当前节点后移：head 指向之前保存的 next 节点
        }
        return prev;
    }
}